package com.huangyi;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static final int N = 1010;

    public static void main(String[] args) {
        // 测试用例
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int V = scanner.nextInt();

        int[] v = new int[N];
        int[] w = new int[N];

        for (int i = 1; i <= n; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }

        Solution s1 = new Solution();
        System.out.println(s1.knapsack(n, V, v, w));

        Solution2 s2 = new Solution2();
        System.out.println(s2.knapsack(n, V, v, w));

        scanner.close();
    }

    // 01背包 - 方案1：不要求装满
    static class Solution {
        public int knapsack(int n, int V, int[] v, int[] w) {
            // 1) dp[i][j] 表示前 i 个物品，容量不超过 j 的最大价值
            int[][] dp = new int[n + 1][V + 1];

            // 2) 初始状态：dp[0][j] = 0（默认值，表示不选任何物品）
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= V; j++) {
                    dp[i][j] = dp[i - 1][j];  // 不选物品 i
                    if (j >= v[i]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
                    }
                }
            }

            // 3) 返回最大价值
            return dp[n][V];
        }
    }

    // 01背包 - 方案2：恰好装满
    static class Solution2 {
        public int knapsack(int n, int V, int[] v, int[] w) {
            // 1) dp[i][j] 表示前 i 个物品，容量恰好为 j 的最大价值
            int[][] dp = new int[n + 1][V + 1];

            // 2) 初始状态：dp[0][0] = 0，dp[0][j] = -1（j>0 时无法装满）
            for (int j = 1; j <= V; j++) {
                dp[0][j] = -1;  // 标记为无效状态
            }

            // 3) 状态转移
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= V; j++) {
                    dp[i][j] = dp[i - 1][j];  // 不选物品 i
                    // 选物品 i：必须判断上一状态是否有效
                    if (j >= v[i] && dp[i - 1][j - v[i]] != -1) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
                    }
                }
            }

            // 4) 返回结果（无解返回 0）
            return dp[n][V] == -1 ? 0 : dp[n][V];
        }
    }
}